Many modern smart phones and other mobile devices (e.g., electronic tablets) include navigation subsystems for allowing a user to track their location or the location of others on a digital map. Satellites, cell towers or network access points (e.g., Wi-Fi) can be used to acquire position data to locate a user on a road in a map database. Using the map database, the navigation system can give directions to other locations along roads also in the map database. Dead reckoning using data from sensors (e.g., accelerometers, gyroscopes) can be used to compute position data when position data is unavailable (e.g., lost satellite signals due to multipath or loss of line of sight).
A map database represents a road network and its associated features. Some examples of features include nodes, links and areas. Each feature can have attributes, such as location coordinates, shape, addresses, road class, speed range, etc. Other information associated with the road network can also be included in the map database, such as points of interest, building shapes, and political boundaries. Map databases can be provided in standardized file formats, such as Geographic Data Files (GDF).
In the map database, each node can represent a point location of the surface of the Earth and can be defined on the a map by a pair of longitude and latitude coordinates. Each link in the map database can represent a stretch of road between two nodes. Links can be represented by a line segment corresponding to a straight section of road or a curve having a shape that can be described by shape points along the link. Curves in the road can be represented by a combination of centroid (point or node), with a radius, and polar coordinates to define the boundaries of the curve. Like nodes, shape points can be defined by longitude and latitude coordinates. Shape points, however, do not connect links. Areas can be two-dimensional shapes that represent things or places, such as parks, cities and blocks. Areas can be defined by boundaries, usually formed by a closed polygon.